package com.demo.datastructure.reorder.mergeSort;

/**
 * @description: 有哨兵的归并排序 特点:先分裂再合并
 * @author: ljr
 * @time: 2021/5/4 16:15
 * @since： 1.0
 */
public class MyMergeSort3 {

    public static void mergeSort(int[] args, int n){
        mergeSortC(args,0,n-1);
    }

    private static void mergeSortC(int[] args, int p, int r) {
         if(p >= r){ return; }
         int d = (p+r)/2;
         mergeSortC(args,p,d);
         mergeSortC(args,d+1,r);
         merge(args,p,r,d);
    }

    private static void merge(int[] args, int p, int r, int c) {
        int[] lefts = new int[c-p+2];
        int[] rights = new int[r-c+1];

        int i = 0;
        for(; i < lefts.length-1; i++){
            lefts[i] = args[p+i];
        }
        lefts[lefts.length-1] = Integer.MAX_VALUE;

        for(i=0; i < rights.length-1; i++){
            rights[i] = args[c+1+i];
        }
        rights[rights.length-1] = Integer.MAX_VALUE;

        i = 0;
        int j = 0;
        int k = p;
        while(k <= r){
            if(lefts[i] <= rights[j]){
                args[k++] = lefts[i++];
            }else{
                args[k++] = rights[j++];
            }
        }

    }


    public static void main(String[] args) {
        int[] nums = new int[]{11,8,3,9,7,1,2,5};
        MyMergeSort3.mergeSort(nums,8);
        for(int num : nums){
            System.out.println(num);
        }
    }

}
